Search Results

Documents authored by Ovens, Sean

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2023.46
Brief Announcement: The Space Complexity of Set Agreement Using Swap

Authors: Sean Ovens

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
We prove that any randomized wait-free n-process k-set agreement algorithm using only swap objects requires at least ⌈n/k⌉-1 objects. We also sketch a proof that any randomized wait-free consensus algorithm using only readable swap objects with domain size b requires at least (n-2)/(3b+1) objects.
Cite as

Sean Ovens. Brief Announcement: The Space Complexity of Set Agreement Using Swap. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 46:1-46:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ovens:LIPIcs.DISC.2023.46,
  author =	{Ovens, Sean},
  title =	{{Brief Announcement: The Space Complexity of Set Agreement Using Swap}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{46:1--46:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.46},
  URN =		{urn:nbn:de:0030-drops-191725},
  doi =		{10.4230/LIPIcs.DISC.2023.46},
  annote =	{Keywords: space complexity, consensus, set agreement, lower bound, shared memory}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.30
The Space Complexity of Scannable Objects with Bounded Components

Authors: Sean Ovens

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
A fundamental task in the asynchronous shared memory model is obtaining a consistent view of a collection of shared objects while they are being modified concurrently by other processes. A scannable object addresses this problem. A scannable object is a sequence of readable objects called components, each of which can be accessed independently. It also supports the Scan operation, which simultaneously reads all of the components of the object. In this paper, we consider the space complexity of an n-process, k-component scannable object implementation from objects with bounded domain sizes. If the value of each component can change only a finite number of times, then there is a simple lock-free implementation from k objects. However, more objects are needed if each component is fully reusable, i.e. for every pair of values v, v', there is a sequence of operations that changes the value of the component from v to v'. We considered the special case of scannable binary objects, where each component has domain {0, 1}, in PODC 2021. Here, we present upper and lower bounds on the space complexity of any n-process implementation of a scannable object O with k fully reusable components from an arbitrary set of objects with bounded domain sizes. We construct a lock-free implementation from k objects of the same types as the components of O along with ⌈n/b⌉ objects with domain size 2^b. By weakening the progress condition to obstruction-freedom, we construct an implementation from k objects of the same types as the components of O along with ⌈n/(b-1)⌉ objects with domain size b. When the domain size of each component and each object used to implement O is equal to b and n ≤ b^k - bk + k, we prove that 1/2⋅ (k + (n-1)/b - log_b n) objects are required. This asymptotically matches our obstruction-free upper bound. When n > b^k - bk + k, we prove that 1/2⋅ (b^{k-1} - {(b-1)k + 1}/b) objects are required. We also present a lower bound on the number of objects needed when the domain sizes of the components and the objects used by the implementation are arbitrary and finite.
Cite as

Sean Ovens. The Space Complexity of Scannable Objects with Bounded Components. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ovens:LIPIcs.DISC.2022.30,
  author =	{Ovens, Sean},
  title =	{{The Space Complexity of Scannable Objects with Bounded Components}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{30:1--30:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.30},
  URN =		{urn:nbn:de:0030-drops-172213},
  doi =		{10.4230/LIPIcs.DISC.2022.30},
  annote =	{Keywords: space complexity, lower bound, shared memory, snapshot object}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact